package com.lch.binary;

/**
 * 普通二分查找
 *
 * 有序数组查找指定值
 *
 * @author 刘晨辉
 * @date 2021/9/24 8:36 上午
 */
public class Binary {

    public static int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 8, 9};
    public static int[] b = new int[]{4, 5, 6, 7, 0, 1, 2};
    public static int length = 10;

    public static void main(String[] args) {
//        System.out.pr
//        intln(methodOne(a, 8));
//        System.out.println(findFirstSearchValue(a, 8));
//        System.out.println(findLastSearchValue(a, 8));
        System.out.println(findSearchValueByArr(b, 1));
    }

    private static int methodOne(int[] a, int searchValue) {

        int low = 0;
        int high = length;
        while (low < high) {
            int mid = (low + high - 1) / 2;
            if (a[mid] > searchValue) {
                high = mid;
            } else if (a[mid] < searchValue) {
                low = mid;
            } else {
                return mid;
            }

        }
        return -1;
    }

    private static int findFirstSearchValue(int[] a, int searchValue) {

        int low = 0;
        int high = length;
        while (low < high) {
            int mid = (low + high - 1) / 2;
            if (a[mid] > searchValue) {
                high = mid;
            } else if (a[mid] < searchValue) {
                low = mid;
            } else {
                if (mid != 0 && a[mid - 1] == searchValue) {
                    high = mid;
                } else {
                    return mid;
                }
            }

        }
        return -1;
    }

    private static int findLastSearchValue(int[] a, int searchValue) {

        int low = 0;
        int high = length;
        while (low < high) {
            int mid = (low + high - 1) / 2;
            if (a[mid] > searchValue) {
                high = mid;
            } else if (a[mid] < searchValue) {
                low = mid;
            } else {
                if (mid + 1 < a.length && a[mid + 1] == searchValue) {
                    low = mid;
                } else {
                    return mid;
                }
            }

        }
        return -1;
    }

    private static int findSearchValueByArr(int[] b, int searchValue) {
        int l = 0;
        int r = b.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (searchValue == b[mid]) {
                return mid;
            }
            if (b[0] <= b[mid]) {
                if (searchValue>b[0] && searchValue <= b[mid]) {
                    r = mid -1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (searchValue >= b[mid] || searchValue >= b[r - 1]) {
                    r = mid - 1;
                } else {
                    l = mid - 1;
                }
            }
        }
        return -1;
    }
}
